package cxydmmszl.chapter03.t032;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

/**
 * <li style="color: red;">Prob</li>
 * 分别用递归和非递归方式实现二叉树先序、中序和后序遍历
 * <li style="color: red;">Desc</li>
 * 分别按照二叉树先序，中序和后序打印所有的节点。<br/><br/>
 * <b>输入描述：</b><br/>
 * &emsp;第一行输入两个整数 n 和 root，<br/>
 * &emsp;n 表示二叉树的总节点个数，root 表示二叉树的根节点。<br/><br/>
 * &emsp;以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，<br/>
 * &emsp;右儿子为 rch（如果 lch 为 0 则表示 fa 没有左儿子，rch同理）。<br/><br/>
 * <b>输出描述：</b><br/>
 * &emsp;输出三行，分别表示二叉树的先序，中序和后序。
 * <li style="color: red;">Link</li> CD161
 *
 * @author habitplus
 * @since 2021-08-29 18:57
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int fa, lch, rch;
        HashMap<Integer, TreeNode> map = new HashMap<>();
        HashMap<Integer, int[]> child = new HashMap<>();
        for (int i = 0; i < n; i++) {
            fa = sc.nextInt();
            lch = sc.nextInt();
            rch = sc.nextInt();

            map.put(fa, new TreeNode(fa));
            child.put(fa, new int[]{lch, rch});
        }

        // 建树
        for (Map.Entry<Integer, int[]> ch : child.entrySet()) {
            map.get(ch.getKey()).left = map.get(ch.getValue()[0]);
            map.get(ch.getKey()).right = map.get(ch.getValue()[1]);
        }

        StringBuilder sb = new StringBuilder();
        preOrderByRecur(map.get(root), sb);
        System.out.println(sb.toString());
        sb.delete(0, sb.length());

        inOrderByRecur(map.get(root), sb);
        System.out.println(sb.toString());
        sb.delete(0, sb.length());

        posOrderByRecur(map.get(root), sb);
        System.out.println(sb.toString());
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static void preOrderByRecur(TreeNode root, StringBuilder sb) {
        if (root == null) return;

        sb.append(root.val).append(" ");
        preOrderByRecur(root.left, sb);
        preOrderByRecur(root.right, sb);
    }

    public static void inOrderByRecur(TreeNode root, StringBuilder sb) {
        if (root == null) return;

        inOrderByRecur(root.left, sb);
        sb.append(root.val).append(" ");
        inOrderByRecur(root.right, sb);
    }

    public static void posOrderByRecur(TreeNode root, StringBuilder sb) {
        if (root == null) return;

        posOrderByRecur(root.left, sb);
        posOrderByRecur(root.right, sb);
        sb.append(root.val).append(" ");
    }

    public static void preOrder(TreeNode root) {
        if (root == null) {
            System.out.println("");
            return;
        }
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node;
        while (!stack.isEmpty()) {
            node = stack.pop();
            sb.append(node.val).append(" ");
            if (node.right != null) stack.push(root.right);
            if (node.left != null) stack.push(root.left);
        }
        System.out.println(sb.toString());
    }

    public static void inOrder(TreeNode root) {
        if (root == null) {
            System.out.println("");
            return;
        }

        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();

        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                sb.append(root.val).append(" ");
                root = root.right;
            }
        }
        System.out.println(sb.toString());
    }

    public static void posOrder(TreeNode root) {
        if (root == null) {
            System.out.println("");
            return;
        }

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);

        while (!s1.isEmpty()) {
            root = s1.pop();
            s2.push(root);
            if (root.left != null) s1.push(root.left);
            if (root.right != null) s1.push(root.right);
        }

        while (!s2.isEmpty()) {
            System.out.print(s2.pop().val + " ");
        }
        System.out.println();
    }

    public static void posOrder02(TreeNode root) {
        if (root == null) {
            System.out.println("");
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode c;

        while (!stack.isEmpty()) {
            c = stack.peek();
            if (c.left != null && root != c.left && root != c.right) {
                stack.push(c.left);
            } else if (c.right != null && root != c.right) {
                stack.push(c.right);
            } else {
                System.out.print(stack.pop().val + " ");
                root = c;
            }
        }
        System.out.println();
    }
}
